package org.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 一个方法团灭 nSum 问题
public class NSum {
    // 1. towSum问题
    // 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
    static class TwoSum {
        int[] twoSum(int[] nums, int target) {
            // 先对数组排序
            Arrays.sort(nums);
            // 左右指针
            int left = 0;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[left] + nums[right];
                // 根据sum和target的比较，移动左右指针
                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else if (sum == target) {
                    return new int[]{nums[left], nums[right]};
                }
            }
            return new int[]{};
        }
    }

    // nums 中可能有多对儿元素之和都等于 target，请你的算法返回所有和为 target 的元素对儿，其中不能出现重复。
    // 注意：下面这种写法明显会出现重复元素的问题，不满足题意
    static class TwoSumReturnMultiple {
        // 基本思路肯定还是排序加双指针
        List<List<Integer>> twoSumTarget(int[] nums, int target) {
            // 先对数组排序
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            int left = 0;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[left] + nums[right];
                // 根据sum和target的比较，移动左右指针
                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else if (sum == target) {
                    res.add(Arrays.asList(nums[left], nums[right]));
                    left++;
                    right--;
                }
            }
            return res;
        }

        // 注意：下面这种写法明显会出现重复元素的问题，满足题意：不重复元素
        List<List<Integer>> twoSumTarget1(int[] nums, int target) {
            Arrays.sort(nums);
            int lo = 0;
            int hi = nums.length - 1;
            List<List<Integer>> res = new ArrayList<>();
            while (lo < hi) {
                int sum = nums[lo] + nums[hi];
                int left = nums[lo], right = nums[hi];
                if (sum < target) {
                    while (lo < hi && nums[lo] == left) {
                        lo++;
                    }
                } else if (sum > target) {
                    while (lo < hi && nums[hi] == right) {
                        hi--;
                    }
                } else {
                    res.add(new ArrayList<>(Arrays.asList(left, right)));
                    while (lo < hi && nums[lo] == left) {
                        lo++;
                    }
                    while (lo < hi && nums[hi] == right) {
                        hi--;
                    }
                }
            }
            // 这样，一个通用化的 twoSum 函数就写出来了，请确保你理解了该算法的逻辑，我们后面解决 3Sum 和 4Sum 的时候会复用这个函数。
            return res;
        }
    }

    // 3Sum 问题
    // 15. 三数之和
    // 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
    // 同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。
    static class ThreeSum {
        List<List<Integer>> threeSum(int[] nums) {
            return this.threeSumTarget(nums, 0);
        }

        List<List<Integer>> threeSumTarget(int[] nums, int target) {
            // 输入数组 nums，返回所有和为 target 的三元组
            // 数组得排个序
            Arrays.sort(nums);
            int n = nums.length;
            List<List<Integer>> res = new ArrayList<>();
            // 穷举threeSum的第一个数字
            for (int i = 0; i < n; i++) {
                // 对target - nums[i]计算twoSum
                List<List<Integer>> tuples = twoSumTarget(nums, i + 1, target - nums[i]);
                // 如果存在满足条件的二元组，再加上nums[i]就是三元组
                for (List<Integer> tuple : tuples) {
                    tuple.add(nums[i]);
                    res.add(tuple);
                }
                // 跳过第一个数字重复的情况，否则会出现重复结果
                while (i < n - 1 && nums[i] == nums[i + 1]) {
                    i++;
                }
            }
            return res;
        }

        // 从 nums[start] 开始，计算有序数组 nums 中所有和为 target 的二元组
        List<List<Integer>> twoSumTarget(int[] nums, int start, int target) {
            int lo = start;
            int hi = nums.length - 1;
            List<List<Integer>> res = new ArrayList<>();
            while (lo < hi) {
                int sum = nums[lo] + nums[hi];
                int left = nums[lo], right = nums[hi];
                if (sum < target) {
                    while (lo < hi && nums[lo] == left) {
                        lo++;
                    }
                } else if (sum > target) {
                    while (lo < hi && nums[hi] == right) {
                        hi--;
                    }
                } else {
                    res.add(new ArrayList<>(Arrays.asList(left, right)));
                    while (lo < hi && nums[lo] == left) {
                        lo++;
                    }
                    while (lo < hi && nums[hi] == right) {
                        hi--;
                    }
                }
            }
            // 这样，一个通用化的 twoSum 函数就写出来了，请确保你理解了该算法的逻辑，我们后面解决 3Sum 和 4Sum 的时候会复用这个函数。
            return res;
        }


        // 双指针法
        public List<List<Integer>> threeSum1(int[] nums) {
            List<List<Integer>> result = new ArrayList<>();
            Arrays.sort(nums);
            // 找出a+b+c=0
            // a=nums[i]; b=nums[left]; c=nums[right];
            for (int i = 0; i < nums.length; i++) {
                // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
                if (nums[i] > 0) {
                    return result;
                }
                if (i > 0 && nums[i] == nums[i - 1]) { // 去重a
                    continue;
                }
                int left = i + 1;
                int right = nums.length - 1;
                while (right > left) {
                    int sum = nums[i] + nums[left] + nums[right];
                    if (sum > 0) {
                        right--;
                    } else if (sum < 0) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                        // 去重逻辑应该放在找到一个三元组之后，对b和c去重
                        while (right > left && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        while (right > left && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        right--;
                        left++;
                    }
                }
            }
            return result;
        }
    }

    // 三、4Sum 问题
    // 18. 四数之和
    // 1 <= nums.length <= 200
    //-109 <= nums[i] <= 109
    //-109 <= target <= 109
    static class FourSum {
        // 这里要注意：本题说了 nums[i] 和 target 的取值都是 [-10^9, 10^9]
        public List<List<Integer>> fourSum(int[] nums, int target) {
            // 数组需要排序
            Arrays.sort(nums);
            int n = nums.length;
            List<List<Integer>> res = new ArrayList<>();
            // 穷举 fourSum 的第一个数
            for (int i = 0; i < n; i++) {
                // 对 target - nums[i] 计算 threeSum
                List<List<Integer>> triples = threeSumTarget(nums, i + 1, target - nums[i]);
                // 如果存在满足条件的三元组，再加上 nums[i] 就是结果四元组
                for (List<Integer> triple : triples) {
                    triple.add(nums[i]);
                    res.add(triple);
                }
                // fourSum 的第一个数不能重复
                while (i < n - 1 && nums[i] == nums[i + 1]) i++;
            }
            return res;
        }

        List<List<Integer>> threeSumTarget(int[] nums, int start, long target) {
            // 输入数组 nums，返回所有和为 target 的三元组
            // 数组得排个序
            Arrays.sort(nums);
            int n = nums.length;
            List<List<Integer>> res = new ArrayList<>();
            // 穷举threeSum的第一个数字
            for (int i = start; i < n; i++) {
                // 对target - nums[i]计算twoSum
                List<List<Integer>> tuples = twoSumTarget(nums, i + 1, target - nums[i]);
                // 如果存在满足条件的二元组，再加上nums[i]就是三元组
                for (List<Integer> tuple : tuples) {
                    tuple.add(nums[i]);
                    res.add(tuple);
                }
                // 跳过第一个数字重复的情况，否则会出现重复结果
                while (i < n - 1 && nums[i] == nums[i + 1]) {
                    i++;
                }
            }
            return res;
        }

        // 从 nums[start] 开始，计算有序数组 nums 中所有和为 target 的二元组
        List<List<Integer>> twoSumTarget(int[] nums, int start, long target) {
            int lo = start;
            int hi = nums.length - 1;
            List<List<Integer>> res = new ArrayList<>();
            while (lo < hi) {
                int sum = nums[lo] + nums[hi];
                int left = nums[lo], right = nums[hi];
                if (sum < target) {
                    while (lo < hi && nums[lo] == left) {
                        lo++;
                    }
                } else if (sum > target) {
                    while (lo < hi && nums[hi] == right) {
                        hi--;
                    }
                } else {
                    res.add(new ArrayList<>(Arrays.asList(left, right)));
                    while (lo < hi && nums[lo] == left) {
                        lo++;
                    }
                    while (lo < hi && nums[hi] == right) {
                        hi--;
                    }
                }
            }
            return res;
        }
    }

    // 四：求100Sum问题？
    static class Template {
        // 注意：调用这个函数之前一定要先给 nums 排序
        // n 填写想求的是几数之和，start 从哪个索引开始计算（一般填 0），target 填想凑出的目标和
        List<List<Integer>> nSumTarget(int[] nums, int n, int start, long target) {
            int sz = nums.length;
            List<List<Integer>> res = new ArrayList<>();
            // 至少2Sum，且数组大小不应该小于n
            if (n < 2 || sz < n) {
                return res;
            }
            // 2Sum是base case
            if (n == 2) {
                // 双指针那一套操作
                int lo = start, hi = sz - 1;
                while (lo < hi) {
                    int sum = nums[lo] + nums[hi];
                    int left = nums[lo], right = nums[hi];
                    if (sum < target) {
                        while (lo < hi && nums[lo] == left) {
                            lo++;
                        }
                    } else if (sum > target) {
                        while (lo < hi && nums[hi] == right) {
                            hi--;
                        }
                    } else {
                        res.add(new ArrayList<>(Arrays.asList(nums[lo], nums[hi])));
                        while (lo < hi && nums[lo] == left) {
                            lo++;
                        }
                        while (lo < hi && nums[hi] == right) {
                            hi--;
                        }
                    }
                }
            } else {
                // n > 2时，递归计算(n-1)Sum的结果
                for (int i = start; i < sz; i++) {
                    List<List<Integer>> sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                    for (List<Integer> arr : sub) {
                        // (n-1)Sum 加上 nums[i] 就是 nSum
                        arr.add(nums[i]);
                        res.add(arr);
                    }
                    while (i < sz - 1 && nums[i] == nums[i + 1]) {
                        i++;
                    }
                }
            }
            return res;
        }
    }
}
